package 力扣题库;

public class p200岛屿数量 {
    public int numIslands(char[][] grid) {
        //回溯算法
        int row=grid.length;
        int column=grid[0].length;

        int count=0;
        for (int i = 0; i <row ; i++) {
            for (int j = 0; j <column ; j++) {
                if (grid[i][j]=='1') {
                    //当前位置是岛屿，就对这个位置进行深度优先搜索，检查与该位置是同一岛屿的其他位置
                    count++;
                    backtrack(grid,i,j);
                }

            }
        }
        return count;
    }

    private void backtrack(char[][] grid, int x, int y) {
        //递归出口
//        if (x<0 || y<0 || x>=grid.length || y>=grid[0].length || grid[x][y] != '1') {
//            //超出矩阵 或者 回到已标记过的岛屿，直接返回
//            return;
//        }

        if (! (x>=0 && x<grid.length && y>=0 && y<grid[0].length)) {
            //超出矩阵 ，直接返回
            return;
        }
        if (grid[x][y] != '1') {
            //当前位置已经检查过 或者 是水域，直接返回
            return;
        }

        grid[x][y]='2';//标记当前搜索的岛屿

        backtrack(grid,x+1,y);
        backtrack(grid,x-1,y);
        backtrack(grid,x,y-1);
        backtrack(grid,x,y+1);
    }
}
